import java.util.PriorityQueue;
import java.util.Stack;

//面试题 03.05. 栈排序
class SortedStack1 {
    // 优先级队列, 队首为最小元素
    private PriorityQueue<Integer> priorityQueue;

    public SortedStack1() {
        priorityQueue = new PriorityQueue<>();
    }

    public void push(int val) {
        priorityQueue.offer(val);
    }

    public void pop() {
        priorityQueue.poll();
    }

    public int peek() {
        if (priorityQueue.isEmpty()) {
            return -1;
        }
        return priorityQueue.peek();
    }

    public boolean isEmpty() {
        return priorityQueue.isEmpty();
    }
}

class SortedStack2 {
    // 单调栈
    // 维持这个向上单调递减
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public SortedStack2() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int val) {
        while (!stack1.isEmpty() && val > stack1.peek()) {
            stack2.push(stack1.pop());
        }
        stack1.push(val);
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
    }

    public void pop() {
        if (isEmpty()) {
            return;
        }
        stack1.pop();
    }

    public int peek() {
        if (stack1.isEmpty()) {
            return -1;
        }
        return stack1.peek();
    }

    public boolean isEmpty() {
        return stack1.isEmpty();
    }
}
public class day230313 {
    //2383. 赢得比赛需要的最少训练时长
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
        int sum = 0;
        for (int e : energy) {
            sum += e;
        }
        int trainingHours = initialEnergy > sum ? 0 : sum + 1 - initialEnergy;

        for (int e : experience) {
            if (initialExperience <= e) {
                trainingHours += 1 + (e - initialExperience);
                initialExperience = 2 * e + 1;
            } else {
                initialExperience += e;
            }
        }
        return trainingHours;
    }
}
